As is known in the art, the basic building block of a 3D graphics chip is a triangle. All objects can be defined as a set of 3D triangles connected together to form complex objects. (A square is made up of 2 triangles; a cube is composed of 12 triangles; and a sphere may be composed of 50-100 triangles.) Now that these triangles have formed the basic shape of the object, the triangle interior must be filled in to give the object its form. The triangle may be filled in as a solid color, shaded to give a gradual change in color across the triangle, or filled in with a predefined pattern. The most complex of these xe2x80x9ctriangle fillxe2x80x9d methods is known as texturing. Texturing is a capability that allows a 2D image/picture to be used to fill the triangle. A simple example is a brick wall. On one hand, this wall could be constructed by hundreds of triangles forming the complex details of the wall, but, on the other hand, a picture of a brick wall could be pasted on a square (two triangles) to obtain the same, if not better, resultant image. Because of the power of texturing, this method has become the cornerstone of 3D graphics programming during the past 10-15 years.
Each distinct image (known as a texture pattern) is defined with a size, the height and width of the image. Texture patterns (for reasons that are not important to this discussion) are defined in size known as the xe2x80x9cPowers of 2xe2x80x9d. The smallest texture pattern is 1xc3x971 and increases upwards to 2xc3x972, 4xc3x974, 8xc3x978, 16xc3x9716, etc (the powers of 2 are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, and so forth).
Unfortunately, when designing a physical graphics chip, the hardware must have certain limits placed on it. One of these limits is the maximum texture pattern size that can be supported. The goal of hardware developers is to keep this limit ahead of what software developers desire to use, and, of course, this is not always the case.
In today""s environment, there are several major developers of 3D graphics chips. NVIDIA(trademark) builds a line of chips that has a limit of 2048xc3x972048 for the Maximum Texture Pattern(trademark); S3(trademark) builds a line of chips that has a limit of 2048xc3x972048; and 3DfX(trademark) builds the Voodoo(trademark) line of chips which are limited to only 256xc3x97256. In the market today, there are games (namely Quake3(trademark) from id Software) that are starting to use texture patterns at a size of 512xc3x97512.
According to one aspect of the invention, a software technique allows larger texture patterns to be managed on graphics chips that do not support the large patterns directly in hardware.
A large texture pattern is divided into several quadrants according to a Powers of 2 technique. If an object triangle does not completely fit within a triangle is decomposed into clipped triangles, each of which completely fits within a quadrant.
According to another aspect of the invention, the process recursively decomposes an object triangle by looking for quadrant crossings along the edges of the triangle.
According to a still further aspect of the invention, for a given triangle vertex, double crossings of both sides from a vertex are processed first. Single crossings are implemented second.
According to a still further aspect of the invention, a system including a CPU, graphics card, and display implements program code to implement the process to allow graphics chips on the card to support larger texture patterns than can be handled by the hardware of the chip.
Additional features and advantages will be apparent in view of the following detailed description and appended drawings.